package no10;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/4/25 15:25
 * 青蛙跳台阶问题
 * https://leetcode.cn/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/
 */
public class Solution02 {

    public int numWays(int n) {
        // 动态规划思想, 青蛙可能从倒数第二级或者倒数第一级台阶跳上来
        // f(1) = 1, f(2) = 2, f(n) = f(n-1) + f(n-2)
        if (n <= 1) {
            return 1;
        }
        int first = 1;
        int second = 2;
        int third = 2; // 初始为2, 便于情况归纳
        for (int i = 3; i <= n; i++) {
            third = (first + second) % 1000000007;
            first = second;
            second = third;
        }
        return third;
    }
}
